package leetCode.solution;

import com.alibaba.fastjson.JSON;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 
 * 子数组 是数组中的一个连续部分。
 * 
 * @author jerry
 * @ClassName: Solution53
 * @Description:TODO(描述这个类的作用)
 * @date 2022年11月25日 下午3:18:01
 */
public class Solution53 {
	public static void main(String[] args) {
		System.out.println(JSON.toJSONString(new Solution53().maxSubArray(new int[] {-2,1})));
	}
	
	// 前缀和不能贡献，就抛弃 从新开始
	public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
        	pre=pre<0?x:pre+x;
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
	
	public int maxSubArray3(int[] nums) {
		int pre = 0, maxAns = nums[0];
		for (int x : nums) {
            pre = Math.max(pre + x, x);
			maxAns = Math.max(maxAns, pre);
		}
		return maxAns;
	}

	
	public int maxSubArray2(int[] nums) {
		if(nums==null || nums.length==0) return 0;
		int n = nums.length;
		int maxSum = Integer.MIN_VALUE;
		int[][] dp = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=i;j<n;j++) {
				if(i==j) {
					dp[i][j]=nums[j];
				}else {
					dp[i][j]=dp[i][j-1]+nums[j];
				}
				maxSum = Math.max(maxSum, dp[i][j]);
			}
		}
		return maxSum;
	}
	
	public int maxSubArray1(int[] nums) {
		if(nums==null || nums.length==0) return 0;
		int[] preSum = new int[nums.length];
		preSum(nums,preSum);
		int maxSum = preSum[0];
		for(int i = 0;i<preSum.length;i++) {
			maxSum = Math.max(maxSum, preSum[i]);
			int j=i-1;
			while(j>=0) {
				maxSum = Math.max(maxSum, preSum[i]-preSum[j--]);
			}
		}
		return maxSum;
	}
	
	private void preSum(int[] nums, int[] preSum) {
		preSum[0]=nums[0];
		for(int i = 1;i<nums.length;i++) {
			preSum[i]=preSum[i-1]+nums[i];
		}
	}
}
